package ljl.alg.hot100;

import commons.TreeNode;

import java.util.LinkedList;

public class _226_invert_bi_tree {
    
    /*
    * 非常的简洁，但我不满足，看看别人怎么写的
    * 这种难度的题，只能让你拿 10k
    * */
    public TreeNode invertTree3(TreeNode root) {
        if (root == null) return null;
        TreeNode left = invertTree(root.left);
        root.left = invertTree(root.right);
        root.right = left;
        return root;
    }
    
    // 无非再来个广度优先和深度优先遍历
    // 原理就是遍历每一个节点，然后交换它的左右子树，感觉上其实没递归好
    // 写一下吧，不吃亏
    
    // bfs
    public TreeNode invertTree2(TreeNode root) {
        if (root == null) return null;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.pop();
            TreeNode t = node.left;
            node.left = node.right;
            node.right = t;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        
        return root;
    }
    
    // dfs 其实还是可以递归，但是和第一种解法就没区别了 就不笨了
    // 我要写笨逼解法
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            TreeNode t = node.left;
            node.left = node.right;
            node.right = t;
            
            // 由于你交换了左右，这里得改成 left！我干！
            root = node.left;
        }
        return p;
    }
    
}
